แนวคิด

ให้ χ {\displaystyle \chi } เป็นเซตของสถานะ และ S เป็นฟังก์ชันจริงซึ่ง S(x) จะให้ค่าความเหมาะสมของ x โดยที่ x เป็นสมาชิกของ χ {\displaystyle \chi } โดยค่า x ที่เหมาะสมที่สุดคือ x* ซึ่งจะทำให้ค่าของ S(x*) มีค่าสูงที่สุด สามารถเขียนเป็นปัญหาในรูปของสมการทางคณิตศาสตร์ได้ดังสมการที่ (6)

S ( x ∗ ) = γ ∗ = m a x x S ( x ) {\displaystyle S(x^{*})=\gamma ^{*}=max_{x}S(x)\,} (6)

หาพิจารณาปัญหานี้เทียบกับปัญหาการประมาณค่าของ H ( x ) = I S ( X ) ≥ γ {\displaystyle H(x)=I_{S(X)\geq \gamma }} เมื่อ X เป็นตัวแปรสุ่มที่มีความหนาแน่นของความน่าจะเป็น f ( x ; u ) {\displaystyle f(x;u)} และให้ γ {\displaystyle \gamma } เป็นค่าระดับชั้น จะสังเกตว่าถ้าค่า γ {\displaystyle \gamma } มีค่าใกล้เคียงกับ γ ∗ {\displaystyle \gamma ^{*}} (ค่าสูงสุดของ S) แล้ว จะทำให้ค่าของ H ( x ) = I S ( X ) ≥ γ {\displaystyle H(x)=I_{S(X)\geq \gamma }} เป็นความน่าจะเป็นของเหตุการณ๊ที่พบเจอได้ยาก ซึ่งปัญหานี้เราจะต้องการสร้างตัวอย่างสุ่มจำนวนหนึ่งที่มีค่าใกล้เคียงกับ x* โดยเป็นเรื่องที่ดีที่วิธีครอส-เอนโทรปี สามารถทำเรื่องนี้ได้

หากเปรียบเทียบความแตกต่างของปัญหาระหว่างการหาค่าที่เหมาะสมที่สุด กับ การประมาณค่า ความแตกต่างก็คือการหาค่าที่เหมาะสมที่สุด เราจะไม่รู้ค่าของระดับชั้น γ = γ ∗ {\displaystyle \gamma =\gamma ^{*}} ล่วงหน้าเหมือนในการประมาณค่า แต่อย่างไรก็ตามขั้นตอนวิธีในการแก้ปัญหาก็ไ่ม่ค่อยแตกต่างกันมากคือเราจะสร้างลำดับของ γ t {\displaystyle \gamma _{t}} และ v ^ t {\displaystyle {\widehat {v}}_{t}} ไปเรื่อยๆ โดยจะพยายามให้ทั้งสองค่าเข้าใกล้ γ ∗ {\displaystyle \gamma ^{*}} และ v ∗ {\displaystyle v^{*}} ตามลำดับ ซึ่งค่าของ v ∗ {\displaystyle v^{*}} จะสอดคล้องกับค่าของ x ∗ {\displaystyle x^{*}} ที่ต้องการหาเช่นกัน

รหัสเทียมสำหรับวิธีครอส-เอนโทรปีเพื่อใช้ในปัญหาการหาค่าที่เหมาะสมที่สุด

 1                                                                         v                ^                                                          0                          =        u              {\displaystyle {\widehat {v}}_{0}=u}    และ  2                               N                      e                          =        ⌈        ρ                N        ⌉              {\displaystyle N^{e}=\lceil \rho \,N\rceil }   3 t = 0 /*ตัวนับจำนวนรอบ*/ 4 5 ทำ 6     t = t + 1 7     สุ่มตัวอย่างสุ่ม                               X                      1                          ,        .        .        .        ,                  X                      N                                        {\displaystyle X_{1},...,X_{N}\,}   ตามความหนาแน่นของความน่าจะเป็น                     f        (        −        :                                                            v                ^                                                          t            −            1                          )                      {\displaystyle f(-:{\widehat {v}}_{t-1})\,}   8     สำหรับทุก i ตั้งแต่ 1 ถึง N 9                                       S                      (            i            )                          =        S        (                  X                      i                          )                      {\displaystyle S_{(i)}=S(X_{i})\,}  10     เรียงลำดับจากน้อยไปหามาก(S)        11                                                                             γ                ^                                                          t                          =                  S                      (            N            −                          N                              e                                      +            1            )                                        {\displaystyle {\widehat {\gamma }}_{t}=S_{(N-N^{e}+1)}\,}  12                                                                             γ                ^                                                          t                                        {\displaystyle {\widehat {\gamma }}_{t}\,}   = ค่าต่ำสุด(                    γ                      {\displaystyle \gamma \,}  ,                                                                        γ                ^                                                          t                                {\displaystyle {\widehat {\gamma }}_{t}}  )13     คำนวณ                     v        =                                                            v                ^                                                          t                                        {\displaystyle v={\widehat {v}}_{t}\,}   ที่ทำให้                                                                         I                                  S                  (                                      X                                          k                                                        )                  ≥                                                                                                              γ                          ^                                                                                                            t                                                                                  l              n              (              f              (                              X                                  k                                            ;              v              )              )                        N                                {\displaystyle {\frac {I_{S(X_{k})\geq {\widehat {\gamma }}_{t}}ln(f(X_{k};v))}{N}}}   สูงที่สุด14 ระหว่างที่ ยังไม่ถึงเงื่อนไขยุติ1516 คืนค่า                                                                         v                ^                                                          t                                        {\displaystyle {\widehat {v}}_{t}\,}  

จะเห็นว่าหากต้องการใช้ขั้นตอนวิธีนี้ต้องทำการปรับค่า v ^ 0 , N , ρ {\displaystyle {\widehat {v}}_{0},N,\rho } และเงื่อนไขยุติให้เหมาะสม